
// 移除链表
public class ReverseLinkedList {

  public static void main(String[] args) {
    
  }

  /**
   * 第一种方法：双指针法
   * 定义两个指针：当前指针cur和之前指针pre
   * cur指向head，pre指向null
   * while循环的终止条件：cur指到最后一个指针，也就是cur不为null
   * 然后要进行翻转：
   * 先保存cur.next，如果不保存的话，翻转后就找不到节点
   * cur.next指向pre
   * 
   * 最后移动pre和cur，循环结束后返回pre头节点
   * 
   * 时间复杂度: O(n)
   * 空间复杂度: O(1)
   */
  // public ListNode reverseList(ListNode head){
  //   ListNode pre = null;
  //   ListNode cur = head;

  //    while(cur != null){
  //     // 转了方向
  //     ListNode temp = cur.next;
  //     cur.next = pre;
  //     pre = cur;
  //     cur = temp;
  //   }

  //   return pre;
  // }

  /**
   * 第二种方法：递归
   * 跟双指针一样的逻辑
   * 只不过移动指针的时候需要递归一下
   * 
   * 时间复杂度: O(n)
   * 空间复杂度: O(n)
   */
  public ListNode reverseList(ListNode head){
    return reverse(null,head);
  }
  public ListNode reverse(ListNode pre,ListNode cur){
    if(cur == null){
      return pre;
    }
    ListNode temp = cur.next;
    cur.next = pre;
    
    return reverse(cur,temp);
  }
  
  // 定义一个指针的节点
  class ListNode {
    // 节点的值
    int val;
    // 下一个节点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {

    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
      this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}
